#include <cstdlib>
#include <cstdio> //perror
#include <algorithm>
#include <queue>
#include <vector>

// 位运算是针对整型运算的
using namespace std;
typedef int Date;
typedef struct BTNode
{
    BTNode *_leftchild;
    BTNode *_rightchild;
    Date _val;
    BTNode(int val = 0)
    {
        _leftchild = _rightchild = nullptr;
        _val = val;
    }
} BTNode;

BTNode *BuyNode(int val)
{
    BTNode *newnode = (BTNode *)malloc(sizeof(BTNode));
    if (nullptr == newnode)
    {
        perror("malloc error");
        return nullptr;
    }
    newnode->_val = val;
    return newnode;
}

// 1.编写一个函数求出二叉树的高度(深度)
int Recursionfunc1(BTNode *root)
{
    if (nullptr == root)
        return 0;
    int val_1 = Recursionfunc1(root->_leftchild);
    int val_2 = Recursionfunc1(root->_rightchild);
    return std::max(val_1, val_2) + 1; // return val_1 > val_2 ? val_1 + 1 : val_2 + 1;
}
int BTreeHeight(BTNode *root)
{
    if (nullptr == root)
        return 0;
    else
        return Recursionfunc1(root);
}

// 2.编写一个函数求出二叉树中叶子节点的个数
void Recursionfunc2(BTNode *root, int &size)
{
    if (nullptr == root)
        return;
    if (nullptr == root->_leftchild && nullptr == root->_rightchild)
    {
        ++size;
        return;
    }
    Recursionfunc2(root->_leftchild, size);
    Recursionfunc2(root->_rightchild, size);
}
int BTLeftNode(BTNode *root)
{
    if (nullptr == root)
        return 0;
    int _size = 0;
    Recursionfunc2(root, _size);
    return _size;
}

// 3.编写一个函数计算出
// int BTSize(BTNode *root)
// {
//     if (nullptr == root)
//         return 0;
// }

// 编写一个函数返回与给定val值相等的节点地址(找到节点地址的好处是可以对该节点的_val进行修改，
// 而不是编写的函数仅仅只返回bool类型的值只用于判断_val值是否存在
// 这里使用的是前序遍历
void Recursionfunc3(BTNode *root, int val, pair<BTNode *, bool> &judge)
{
    if (nullptr == root)
        return;
    if (val == root->_val)
    {
        judge.first = root;
        judge.second = true;
        return;
    }
    if (judge.second)
        return;
    Recursionfunc3(root->_leftchild, val, judge);
    Recursionfunc3(root->_rightchild, val, judge);
}
BTNode *BTreeFind(BTNode *root, int val) //_judge变量用于检查node是否已被修改，如果被修改已经找到了节点
{
    BTNode *node = nullptr;
    pair<BTNode *, bool> _judge(nullptr, false);
    Recursionfunc3(root, val, _judge);

    return _judge.first;
}



// 编写一个函数能够层序遍历返回二叉树的值
vector<int> ScanBtree(BTNode *root)
{
    if (nullptr == root)
        return {};
    vector<int> v;
    queue<BTNode *> q;
    q.push(root);
    while (!q.empty())
    {
        BTNode *tmp = q.front();
        v.emplace_back(tmp->_val);
        q.pop();
        if (tmp->_leftchild)
            q.push(tmp->_leftchild);
        if (tmp->_rightchild)
            q.push(tmp->_rightchild);
    }
    return v;
}


//二叉树的层序遍历
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right)
    :val(x), left(left),
    right(right) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv; //注意：结合题意考虑二叉树为空时
        if (nullptr == root)
            return vv;
        // vv.push_back({root->val});
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) 
        {
            vector<int> tmp;
            TreeNode* judgenode = q.back();
            while (true) 
            {
                TreeNode* cur = q.front();
                if (cur == judgenode) {
                    tmp.emplace_back(cur->val);
                    PushNode(q,cur);
                    q.pop();
                    vv.push_back(tmp);
                    tmp.clear();
                    break;
                }
                tmp.emplace_back(cur->val);
                PushNode(q,cur);
                q.pop();
            }
        }
        return vv;
    }
    //向队列中插入节点地址的函数
    void PushNode(queue<TreeNode*>& q, TreeNode* cur) 
    {
        if (cur->left)
            q.push(cur->left);
        if (cur->right)
            q.push(cur->right);
    }
};